/*
 * ImmediateLeftRecursionLeftCornerTransformer.java
 *
 * Created on January 4, 2007, 11:55 AM
 *
 * Takes a <code>Tree</code> and performs a subset of the selective left-corner
 * tree transformations described in Johnson and Roark (2000), returning the transformed
 * tree.
 *
 * This subset is described as follows: only those instantiations of _immediately
 * left-recursive_ rules (i.e., rules of the form A --> A...) trigger the selective
 * left-corner transform.
 *
 * We assume that the <code>Tree</code> has been made "context free" (i.e., that all empty
 * elements -- traces, etc. -- have been removed), although this is not absolutely necessary.
 */

package galronnlp.util;

import galronnlp.io.PennTreeReader;
import java.io.BufferedReader;
import java.io.StringReader;
import java.util.Iterator;
import java.util.LinkedList;
import galronnlp.util.TreeFactory;

/**
 *
 * @author Dennis N. Mehay
 */
public class ImmediateLeftRecursionLeftCornerTransformer {
    
    private SymbolGenerator gen = null;
    public static final String LC_MARK = "/";
    /** Creates a new instance of ImmediateLeftRecursionLeftCornerTransform */
    public ImmediateLeftRecursionLeftCornerTransformer() { this(new SymbolGenerator()); }
    
    public ImmediateLeftRecursionLeftCornerTransformer(SymbolGenerator gen) {
        this.gen = gen;
    }
    
    /**
     * Performs the subset of selective left-corner transform operations as
     * described above.
     */
    public Tree ILRTransform(Tree t) {
        if(t.type()==Tree.LEXICAL) {
            return t;
        } else {
            String lhsCat = t.cat().toString().trim();
            Iterator<Tree> children = t.getChildren().iterator();
            Tree firstRhs = children.next();
            String firstRhsCat = firstRhs.cat().toString().trim();
            if(!(lhsCat.trim().equals(firstRhsCat.trim()))) {
                // Return a new tree where the children have (possibly)
                // been transformed.
                LinkedList<Tree> transformedChildren = new LinkedList<Tree>();
                transformedChildren.addLast(this.ILRTransform(firstRhs));
                while(children.hasNext()) {
                    transformedChildren.addLast(this.ILRTransform(children.next()));
                }
                return TreeFactory.makeTree(t.cat(), transformedChildren);
            } else {
                // Peform a left-corner transform with lhsCat (the current root)
                // as the root.
                String lcBaseCat = t.cat().toString().trim();
                Tree tempResult = t, tempLRHS = firstRhs;
                while((tempLRHS.cat().toString()).trim().equals(lcBaseCat) &&
                        tempLRHS.type()!=Tree.LEXICAL) {
                    tempResult = this.makeLCTree(tempResult);
                    tempLRHS = ((Tree)(tempResult.getChildren().getFirst()));
                }
                
                LinkedList<Tree> lastChildren = tempResult.getChildren();
                Iterator<Tree> lastChildrenIt = lastChildren.iterator();
                LinkedList<Tree> rezes = new LinkedList<Tree>();
                Tree tempT = null;
                //rezes.addLast(lastChildrenIt.next());
                while(lastChildrenIt.hasNext()) {
                    tempT = lastChildrenIt.next();
                    if(lastChildrenIt.hasNext()) {
                        rezes.addLast(this.ILRTransform(tempT));
                    } else {
                        rezes.addLast(tempT);
                    }
                }
                return TreeFactory.makeTree(gen.create(lcBaseCat),rezes);
            }
        }
    }
    
    /**
     * Reverses the selective left-corner transform on a <code>Tree</code> that
     * has been transformed as in <code>ILRTransform</code>.
     *
     * @param lcTree A <code>Tree</code> to be returned to its (possibly) erstwhile
     *               immediately left-recursive state.
     * @return A <code>Tree</code> that is now in its (possibly) left-recursive former state.
     */
    public Tree lcReverse(Tree lcTree) {
        if(lcTree.type()==Tree.LEXICAL)
            return lcTree;
        else {
            Symbol lcCat = lcTree.cat();
            LinkedList<Tree> children = lcTree.getChildren(),
                    rezes = new LinkedList<Tree>();
            Tree rrhs = children.getLast();
            if(rrhs.cat().toString().contains(this.LC_MARK)) {
                Tree tempResult = lcTree, tempRRHS = rrhs;
                while(tempRRHS.type()!=Tree.LEXICAL && tempRRHS.cat().toString().contains(this.LC_MARK)) {
                    tempResult = this.unmakeLCTree(tempResult);
                    tempRRHS = ((Tree)(tempResult.getChildren().getLast()));
                }
                Iterator<Tree> raisedUpChildren = tempResult.getChildren().iterator();
                Tree c = raisedUpChildren.next();
                rezes.addLast(c);
                while(raisedUpChildren.hasNext()) {
                    c=raisedUpChildren.next();
                    rezes.addLast(this.lcReverse(c));
                }
                // *** return ***
                return TreeFactory.makeTree(lcCat, rezes);
            } else {
                Iterator<Tree> kids = children.iterator();
                while(kids.hasNext()) {
                    rezes.addLast(this.lcReverse(kids.next()));
                }
                // *** return ***
                return TreeFactory.makeTree(lcCat, rezes);
            }
        }
    }
    
    /**
     * "Unmakes" one step in the recursive process of the left-corner transform.
     * Takes a <code>Tree</code> instatiating something of the form:
     * A -> c...d P/A[l...m] and returns A -> P[rlc(c)...rlc(d)] l...m
     * where rlc(...) is a (mutually) recursive call to the left-corner reversal method
     * <code>this.lcReverse</code>.  The iteration in the outer, calling method is responsible for
     * reversing any lc-transforms in l...m.
     *
     * @param lcTree A <code>Tree</code> whose lc-transform shape is to be "unmade" by one step.
     * @return A <code>Tree</code> where the rightmost node (that was previously a right-recursive
     *         representation of a left-recursive original tree) is now "unmade" back (closer) to its
     *         left-recursive form by one step.
     */
    public Tree unmakeLCTree(Tree lcTree) {
        String newDomCat = lcTree.cat().toString().trim(); 
        Iterator<Tree> lcKids = lcTree.getChildren().iterator();
        LinkedList<Tree> newLHSTreeKids = new LinkedList<Tree>(),
                newTopLevelKids = new LinkedList<Tree>(),
                farRHKids = ((Tree)(lcTree.getChildren().getLast())).getChildren();
        Tree temp = null;
        while(lcKids.hasNext()) {
            temp = lcKids.next();
            // Is this the very last child? (If so, we already have its children in farRHKids.)
            if(lcKids.hasNext()) {
                newLHSTreeKids.addLast(this.lcReverse(temp));                
            }
        }
        newTopLevelKids.addLast(TreeFactory.makeTree(this.gen.create(newDomCat), newLHSTreeKids));
        newTopLevelKids.addAll(farRHKids);            
        return TreeFactory.makeTree(this.gen.create(newDomCat), newTopLevelKids);
    }
    
    /**
     * Makes a <code>Tree</code> for a recursive step in the
     * left-corner transform.  Takes a Tree which instantiates C -> C[b1...b2] c...d,
     * returns a tree which instantiates
     * C -> b1 ... b2 C/C[t(c)...t(d)], where and t(...) is a recursive call to the 
     * <code>this.ILRTransform</code> left-corner transform method above.
     *
     * @param t A <code>Tree</code>.
     * @return A <code>Tree</code> that completes one step in the left-corner transform
     *         recursion.
     */
    private Tree makeLCTree(Tree t) {
        LinkedList<Tree> children = t.getChildren();
        LinkedList<Tree> tempRez = new LinkedList<Tree>();
        Iterator<Tree> it = children.iterator();
        Tree first = it.next();
        String firstCat = first.cat().toString().trim();
        Iterator<Tree> leftmostChildren = first.getChildren().iterator();
        for(;leftmostChildren.hasNext(); ){
            tempRez.addLast(leftmostChildren.next());
        }
        Tree temp = null, punct = null;
        LinkedList<Tree> tempRez2 = new LinkedList<Tree>();
        for(;it.hasNext();) {
            temp = it.next();
            tempRez2.addLast(this.ILRTransform(temp));
        }
        Tree rightmostChild = TreeFactory.makeTree(this.gen.create(firstCat + this.LC_MARK + firstCat),tempRez2);
        tempRez.addLast(rightmostChild);
        return TreeFactory.makeTree(gen.create(t.cat().toString().trim()),
                tempRez);
    }
    
    /**
     * Takes a <code>Tree</code> that has had the selective left-corner transform
     * applied to it at all immediately left-recursive nodes and converts it to
     * an unambiguously equivalent "flat" structure (see Collins and Roark (2004) or
     * Roark's PhD thesis).  E.g., if Node[A...Z] is a node that dominates nodes A...Z,
     * flatten(T) (T=a tree that instantiates NP -> A...Z NP/NP[Q...P NP/NP[Z...W]])
     * gives a tree that instantiates:
     * NP -> flatten(A)...flatten(Z) NP/NP[flatten(P)...flatten(Q)] flatten(NP/NP[Z...W]).
     *
     * @param lcTree A <code>Tree</code> that has been transformed with the (very) selective
     *               left-corner transform method <code>ILRTransform</code>.
     * @return A <code>Tree</code> that has been "flattened" as described above.
     */
    public Tree flatten(Tree lcTree) {
        if(lcTree.type()==Tree.LEXICAL)
            return lcTree;
        else {
            Iterator<Tree> children = lcTree.getChildren().iterator();
            String domCat = lcTree.cat().toString();
            // Just recurse on all children but the last (that's where we'll need
            // to flatten.
            LinkedList<Tree> resList = new LinkedList<Tree>();
            Tree currentChild = null;
            for(;children.hasNext();) {
                currentChild = children.next();
                // Make sure this isn't the absolute last.
                if(children.hasNext()) {
                    resList.addLast(this.flatten(currentChild));
                } else {
                    if(currentChild.cat().toString().trim().contains(this.LC_MARK)) {
                        Iterator<Tree> flatLCRecursion =
                                this.flattenHelper(currentChild);
                        for(Tree nxt = null; flatLCRecursion.hasNext(); ) {
                            nxt = flatLCRecursion.next();
                            resList.addLast(nxt);
                        }
                    } else {
                        resList.addLast(this.flatten(currentChild));
                    }
                }
            }
            return TreeFactory.makeTree(this.gen.create(domCat), resList);
        }
    }
    
    /**
     * Takes a tree of the form C/B[A...Z D/E[Q...P ...]] and returns an Iterator of
     * <code>Tree</code>s of the form:
     * C/B[flatten(A)...flatten(Z)] D/E[flatten(Q)...flatten(P) flatten(...)]
     * where the final ... is not an instance of a tree whose dominating node is of the
     * form .../...
     *
     * @param lcTrace A <code>Tree</code> of the form C/C[...], where we want to "pull out"
     *                the lower subtrees that are also of the form C/C (and so on recursively...
     *                or iteratively, depending on the implementation).  All other subtrees
     *                are simply passed off in (mutual) recursion to <code>flatten</code>.
     */
    public Iterator<Tree> flattenHelper(Tree lcTrace) {
        LinkedList<Tree> tempList = new LinkedList<Tree>(),
                finalRezList = new LinkedList<Tree>();
        String currDomCat = lcTrace.cat().toString();
        Iterator<Tree> cdcChildren = lcTrace.getChildren().iterator();
        Tree currChild = null;
        for(;cdcChildren.hasNext();) {
            currChild = cdcChildren.next();
            if(cdcChildren.hasNext()) {
                // We're not at the rightmost child.
                tempList.addLast(this.flatten(currChild));
            } else {
                if(currChild.cat().toString().contains(this.LC_MARK)) {
                    // The last child is of the form A/B, so "pull" this subtree
                    // "up" as one step in "flattening" the whole tree (after adding what we've
                    // accomplished from previous iterations (and flattenings), of course).
                    finalRezList.addLast(TreeFactory.makeTree(this.gen.create(currDomCat),
                            tempList));
                    currDomCat = currChild.cat().toString();
                    tempList = new LinkedList<Tree>();
                    cdcChildren = currChild.getChildren().iterator();
                } else {
                    // Otherwise, add what we've build up to the final result.
                    tempList.addLast(this.flatten(currChild));
                    finalRezList.addLast(TreeFactory.makeTree(this.gen.create(currDomCat),
                            tempList));
                }
            }
        }
        return finalRezList.iterator();
    }
    
    /**
     * Performs the inverse of the <code>flatten</code> method.
     * @param fTree An unambiguously equivalent, "flattened" <code>Tree</code>, representing
     *              a left-corner transformed CFG instance (as in Collins and Roark (2004)
     *              or Roark's dissertation) -- actually, any <code>Tree</code> is legal input...
     *              there just wouldn't be much point in passing in any other kind than that mentioned.
     *
     * @return An "unflattened" (i.e., standard left-corner transformed) representation of the tree.
     */
    public Tree unflatten(Tree fTree) {
        if(fTree.type()==Tree.LEXICAL)
            return fTree;
        else {
            // The easiest way is to "unflatten" the Tree from the right-hand side
            // (the opposite of the way we flattened it).
            LinkedList<Tree> fTreesChildren = fTree.getChildren(),
                    tempChildren = null,
                    newChildren = new LinkedList<Tree>();
            Tree unflattenedRRHS = null, temp = null;
            Tree child = fTreesChildren.pollLast();
            for(; child!=null; child = fTreesChildren.pollLast()) {
                if(child.cat().toString().contains(this.LC_MARK)) {
                    temp = this.unflatten(child);
                    if(unflattenedRRHS==null)
                        unflattenedRRHS = temp; // As it were, the base of the unflattening.
                    else {
                        tempChildren = temp.getChildren();
                        tempChildren.addLast(unflattenedRRHS);
                        unflattenedRRHS = TreeFactory.makeTree(temp.cat(),
                                tempChildren);
                    }
                } else {
                    if(unflattenedRRHS!=null) {
                        // Add the unflattened subresult (if any) to the final result.
                        newChildren.addFirst(unflattenedRRHS);
                        unflattenedRRHS = null;
                        newChildren.addFirst(this.unflatten(child));
                    } else {
                        child = this.unflatten(child);
                        newChildren.addFirst(child);
                    }
                }
            }
            return TreeFactory.makeTree(fTree.cat(), newChildren);
        }
    }
    
    ///** 
    // * Creates a tree of the appropriate arity.
    // * @param rootCat A <code>Sybol</code> representing the (immediately) dominating
    // *                category.
    // * @param children
    // */
    //private Tree makeAppropriateTree(Symbol rootCat, LinkedList<Tree> children) {
    //    return TreeFactory.makeTree(rootCat, children);
    //    //if(children.size()==1) {
    //    //    return new UnaryTree(rootCat,children.get(0));
    //    //} else if(children.size()==2) {
    //    //    return new BinaryTree(rootCat,
    //    //            children.get(0),
    //    //            children.get(1));
    //    //} else {
    //    //    return new NaryTree(rootCat,children);
    //    //}
    // }
    
    public static void main(String[] args) {}    
} // end class ImmediateLeftRecursionLeftCornerTransformer
